package leecode.链表;

/**
 * description:
 * author: wangxi
 * date:  2022/5/5 4:28 下午
 *
 * https://leetcode-cn.com/problems/reorder-list/
 *
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 *
 **/
public class ReorderList {

     // Definition for singly-linked list.
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    /**
     * 1. 寻找中间节点，断开
     * 2. 逆转后半部分
     * 3. 合并2个链表，z字形合并
     */
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head1 = head;
        ListNode head2 = slow.next;
        slow.next = null;
        ListNode reverseHead2 = reverse(head2);
        while (head1 != null && reverseHead2 != null) {
            ListNode nextNode1 = head1.next;
            ListNode nextNode2 = reverseHead2.next;
            head1.next = reverseHead2;
            head1 = nextNode1;
            reverseHead2.next = head1;
            reverseHead2 = nextNode2;
        }
    }

    private ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode reverseHead = null;
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode nextNode = cur.next;
            if (nextNode == null) {
                reverseHead = cur;
            }
            cur.next = pre;
            pre = cur;
            cur = nextNode;
        }
        return reverseHead;
    }
}
